package pars;

import ic.ast.Node;
import ic.ast.decl.ClassType;
import ic.ast.decl.DeclClass;
import ic.ast.decl.DeclField;
import ic.ast.decl.DeclLibraryMethod;
import ic.ast.decl.DeclMethod;
import ic.ast.decl.DeclStaticMethod;
import ic.ast.decl.DeclVirtualMethod;
import ic.ast.decl.Parameter;
import ic.ast.decl.PrimitiveType;
import ic.ast.decl.Program;
import ic.ast.decl.PrimitiveType.DataType;
import ic.ast.decl.Type;
import ic.ast.expr.BinaryOp;
import ic.ast.expr.Call;
import ic.ast.expr.Expression;
import ic.ast.expr.Length;
import ic.ast.expr.Literal;
import ic.ast.expr.NewArray;
import ic.ast.expr.NewInstance;
import ic.ast.expr.Ref;
import ic.ast.expr.RefArrayElement;
import ic.ast.expr.RefField;
import ic.ast.expr.RefVariable;
import ic.ast.expr.StaticCall;
import ic.ast.expr.This;
import ic.ast.expr.UnaryOp;
import ic.ast.expr.VirtualCall;
import ic.ast.stmt.LocalVariable;
import ic.ast.stmt.Statement;
import ic.ast.stmt.StmtAssignment;
import ic.ast.stmt.StmtBlock;
import ic.ast.stmt.StmtBreak;
import ic.ast.stmt.StmtCall;
import ic.ast.stmt.StmtContinue;
import ic.ast.stmt.StmtIf;
import ic.ast.stmt.StmtReturn;
import ic.ast.stmt.StmtWhile;

import java.util.*;

import pars.helpers.PumpNode;
import fun.grammar.Grammar;
import fun.grammar.Word;
import fun.parser.earley.EarleyParser;
import fun.parser.earley.EarleyParser.PostMortem;
import fun.parser.earley.EarleyState;
import lex.Token;


public class Calc {

	public Tree process(Iterable<Token> expression, String inputGrammar) throws Exception {
		Grammar g = new Grammar(inputGrammar);
		EarleyParser p = new EarleyParser(expression, g);
		List<EarleyState> completedParses = p.getCompletedParses();
		if (completedParses.isEmpty()) {
			String error = diagnoseError(p.diagnoseError());
			throw new Exception(error);

		} else if (completedParses.size() > 1) {
			throw new Exception("Ambiguous");
		} 
		fun.parser.Tree eTree = completedParses.get(0).parseTree();
		return parseTree(eTree);
	}
	
	private String diagnoseError(PostMortem postMortem) {
		Token lastTerminal = (Token)postMortem.token;
		String[] exptecting; 
		exptecting = postMortem.expecting.toArray(new String[postMortem.expecting.size()]);
		StringBuilder errorMessageBuilder = new StringBuilder();
		String prefix = lastTerminal != null ? lastTerminal.line + ":" + lastTerminal.column : "at end of input";
		errorMessageBuilder.append(prefix + " : syntax error;");
		if (exptecting.length>0){
			errorMessageBuilder.append(" expected ");
			for (int i=0;i<exptecting.length-1;i++){
				errorMessageBuilder.append("'" + exptecting[i] + "' or ");
			}
			errorMessageBuilder.append("'" + exptecting[exptecting.length - 1] + "'");
		}
		if (lastTerminal != null){
			errorMessageBuilder.append(", but found '" + lastTerminal.tag + "'");
		}
		return errorMessageBuilder.toString();
	}

	public Tree parseTree(fun.parser.Tree eTree) throws Exception
	{
		if(eTree.root.tag.equals("UnOp")){
			eTree=foldUnOpToNegativeLiteralIfNeeded(eTree);
		}
		List<Tree> subTrees = new ArrayList<Tree>();	
		for (fun.parser.Tree subTree:eTree.subtrees){
			Tree sibling = parseTree(subTree);
			if (sibling != null){
				if (sibling.root instanceof PumpNode){
					// If sibling is a pump node concatenate its children to its parent.
					subTrees.addAll(Arrays.asList(sibling.subtrees));
				} else {
					subTrees.add(sibling);
				}
			}
		}

		Node root = null;
		switch (eTree.root.tag) {
			case "Program":
				root = CreateProgram(subTrees);
				break;
			case "ClassDecl":
			case "LibraryClass":
				root = CreateDeclClass(eTree, subTrees);
				break;
			case "Field":
				return CreateDeclFieldTree(eTree, subTrees); 
				// We return this tree since fields handling require a pump node generation 
				// which is already create in the CreateDeclFieldTree method.
			case "Method":
			case "LibMethod":
				root = CreateDeclMethod(eTree, subTrees);
				break;
			case "Type":
				root = CreateType(eTree, subTrees);
				if (((Type)root).getArrayDimension() > 0){
					subTrees.clear();
					// Remove type children from array
				}
				break;
			case "FunctionReturnType":
				if (eTree.subtrees.size() < 1){
					throw new Exception("Sub Trees size in FunctionReturnType");
				}
				if (eTree.subtrees.get(0).root.tag == "void"){
					// If the function return type is void we return it
					root = new PrimitiveType(((Token)eTree.subtrees.get(0).root).line, DataType.VOID);
				} else {
					// If not we pass the Type tree which is a child FunctionReturnType
					return subTrees.get(0);
				}
				break;
			case "Formals":
			case "TypeConcat":
				if (subTrees.size() == 0){
					return null;
				} else {
					// If TypeConcat does not derive to epsilon it contains a parameter.
					// Since Type was already parsed (Formals => Type ID TypeConcat)
					// We create a new AstTree for the parameter and set the Type as its child.
					if (eTree.subtrees.size() < 1){
						throw new Exception("Sub Trees size in TypeConcat");
					}
					Tree parsedTypeTree = subTrees.get(0);
					Tree parameterTypeTree[] = {parsedTypeTree};
					if (!(parsedTypeTree.root instanceof Type)){
						throw new Exception("child is not Type in TypeConcat");
					}
					subTrees.set(0, new Tree(CreateParameter(eTree, ((Type)parsedTypeTree.root)), parameterTypeTree));
					// From this point on Format and TypeConcat behave like a PumpNode.
					root = new PumpNode();
				}
				break;
			case "ClassPump":
			case "ClassBodyPump":
			case "StmtPump":
			case "ExprOptional":
			case "ExprConcat":
			case "LibMethodPump":
				if (subTrees.size() == 0){
					return null;
				} else {
					root = new PumpNode();
				}
				break;
			case "StmtBlock":
				if (subTrees.size() > 1){
					root = CreateStmtBlock(eTree, subTrees);
				}
				if(subTrees.size() == 1){
					// Pass child for case when parent is just logic (e.g. S)
					return subTrees.get(0);
				}
				break;
			case "NewVar":
				root = CreateLocalVariable(eTree, subTrees);
				break;
			case "WithOutExpr":
				root = CreateStmtWoExpr(eTree, subTrees);
				break;
			case "RET":
				root = CreateReturnStmt(eTree, subTrees);
				break;
			case "Assignment":
				root = CreateStmtAssignment(eTree, subTrees);
				break;
			case "LOOP":
				root = CreateWhileStmt(eTree, subTrees);
				break;
			case "IfStmt":
			case "IfElseStmt":
			case "IfElsePump":
				if (subTrees.size()>1){
					root = CreateIfStmt(eTree, subTrees);
				}
				// (IfStmt size == 1 => return subTrees.get(0), IfElsePump size == 0 => return null)
				if(subTrees.size() == 1){
					// Pass child for case when parent is just logic (e.g. S)
					return subTrees.get(0);
				} else if (subTrees.size() == 0) {
					return null;
				}
				break;
			case "NewExpr":
				root = CreateNewExpr(eTree, subTrees);
				break;
			case "TermExpr":
				root = CreateTermExpr(eTree, subTrees);
				break;
			case "OR":
			case "AND":
			case "IEQ":
			case "INEQ":
			case "AddSub":
			case "MDR":
				root = CreateBinaryExpr(eTree, subTrees);
				break;	
			case "UnOp":
				root = CreateUnaryExpr(eTree, subTrees);
				break;
			
			case "Location":
				root = CreateRef(eTree, subTrees);
				break;
			case "Literal":
				root = CreateLiteral(eTree, subTrees);
				break;
			case "StaticCall":
			case "VirtualCall":
				root = CreateCall(eTree, subTrees);
				break;
			default:
				if(subTrees.size() == 1){
					// Pass child for case when parent is just logic (e.g. S)
					return subTrees.get(0);
				} else if (subTrees.size() == 0) {
					return null;
				}
		}
		if (root == null){
			throw new Exception("Unable to parse Ast root noot: " + eTree.root.tag); // Should not get here
		}
		return new Tree(root, subTrees.toArray(new Tree[subTrees.size()]));
	}
	
	/// This method folds an unary operator with two children: one the negative sign (-), 
	/// and 2. a numeric literal to a single negative numeric literal.
	private fun.parser.Tree foldUnOpToNegativeLiteralIfNeeded(fun.parser.Tree eTree){
		if(eTree.subtrees.size()<=1)
		{
			return eTree;
		}
		
		/* check if newExpr is derived into an INTEGER literal */
		fun.parser.Tree newExprTree=eTree.subtrees.get(2);
		if(!(newExprTree.root.tag.equals("NewExpr"))){
			return eTree;
		}
			
		fun.parser.Tree finExprTree=newExprTree.subtrees.get(0);
		if(!(finExprTree.root.tag.equals("FinExpr"))){
			return eTree;
		}
			
		fun.parser.Tree termExprTree=finExprTree.subtrees.get(0);
		if(!(termExprTree.root.tag.equals("TermExpr"))){
			return eTree;
		}
		
		fun.parser.Tree literalTree=termExprTree.subtrees.get(0);
		if(!(literalTree.root.tag.equals("Literal"))){
			return eTree;
		}
		
		fun.parser.Tree valueNode = literalTree.subtrees.get(0);
		if(!(valueNode.root.tag.equals("INTEGER"))){
			return eTree;
		}
			
		/* if rightmost derived operator is "-" */
		if(!(eTree.subtrees.get(1).subtrees.get(0).root.tag.equals("-"))){
			return eTree;
		}
		
		Token valueNodeToken = (Token)valueNode.root; /* the number itself */
		valueNodeToken.text ="-" + valueNodeToken.text; /* add - to the literal */
			
		if(eTree.subtrees.get(0).subtrees.size()>0){ /* if number of unary operators is  > 1 because unSymbolPump didn't derive epsilon */
			fun.parser.Tree unSymbolPumpChild=eTree.subtrees.get(0);
			eTree.subtrees.set(0, unSymbolPumpChild.subtrees.get(0)); // Fold the unSymbolPump one level upward if needed
			eTree.subtrees.set(1, unSymbolPumpChild.subtrees.get(1)); // Retrieve the unSymbolPump's unSymbol token and place in the right most unSymbol
			return eTree;
		}
			
		/* if number of unary operators is 1 */
		eTree = literalTree;
		return eTree;
	}
	
	private Call CreateCall(fun.parser.Tree eTree, List<Tree> subTrees) throws Exception{
		Call call = null;
		if (eTree.subtrees.size()<1){
			throw new Exception("Early tree SubTrees size in " + eTree.root.tag);
		}
		List<Expression> arguments = new ArrayList<>();
		for (Tree subAstTree:subTrees){
			if (subAstTree.root instanceof Expression){
				arguments.add((Expression)subAstTree.root);
			}
		}
		if (eTree.subtrees.get(0).root.tag.equals("CLASS_ID")){
			Token classIdToken = (Token)eTree.subtrees.get(0).root;
			CheckEarleyTreeValues(eTree.subtrees, 3, 2, Token.class, eTree.root.tag);
			Token methodIdToken = (Token)eTree.subtrees.get(2).root;
			call = new StaticCall(classIdToken.line, classIdToken.text, methodIdToken.text, arguments);
		} else if (eTree.subtrees.get(0).root.tag.equals("ID")){
			CheckEarleyTreeValues(eTree.subtrees, 1, 0, Token.class, eTree.root.tag);
			Token methodIdToken = (Token)eTree.subtrees.get(0).root;
			call = new VirtualCall(methodIdToken.line, methodIdToken.text, arguments);
		} else if (eTree.subtrees.get(0).root.tag.equals("NewExpr")){
			CheckEarleyTreeValues(eTree.subtrees, 3, 2, Token.class, eTree.root.tag);
			Token methodIdToken = (Token)eTree.subtrees.get(2).root;
			Expression object = arguments.remove(0); // Get the first argument that was parsed as an expression since it was the object name (and not actually an argument)
			call = new VirtualCall(methodIdToken.line, object, methodIdToken.text, arguments);
		} else {
			throw new Exception("Unable to parse Ast Call AstNode under" + eTree.root.tag); // Should not get here
		}
		return call;
	}

	// Declarations
	
	private Program CreateProgram(List<Tree> subAstTree) throws Exception {
		List<DeclClass> declClasses = new ArrayList<DeclClass>();
		for (Tree subTree:subAstTree){
			try {
				declClasses.add((DeclClass)subTree.root);
			}
			catch (ClassCastException e) {
				throw new Exception("Unable to parse Program root node."); // Should not get here
			}
		}
		return new Program(declClasses);
	}
	
	private DeclClass CreateDeclClass(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception {
		List<DeclField> fields = new ArrayList<>();
		List<DeclMethod> methods = new ArrayList<>();
		for (Tree subTree:subAstTrees){
			if (subTree.root instanceof DeclField)
			{
				fields.add((DeclField)subTree.root);
			}
			else if (subTree.root instanceof DeclMethod)
			{
				methods.add((DeclMethod)subTree.root);
			} else {
				// Handle error
			}
		}
		CheckEarleyTreeValues(earleyTree.subtrees, 3, 1, Token.class, "DeclClass");
		Token classToken = (Token)earleyTree.subtrees.get(1).root;
		fun.parser.Tree superClassEarleyTree = earleyTree.subtrees.get(2);
		if (superClassEarleyTree.subtrees.size() > 0){
			CheckEarleyTreeValues(superClassEarleyTree.subtrees, 2, 1, Token.class, "DeclClass-superClass");
			String superClassName = ((Token)superClassEarleyTree.subtrees.get(1).root).text;
			return new DeclClass(classToken.line, classToken.text, superClassName, 
								fields, 
								methods);
		}
		return new DeclClass(classToken.line, 
							classToken.text, 
							fields, 
							methods);
	}
	
	private Tree CreateDeclFieldTree(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception {
		Type type=null;
		for (Tree subTree:subAstTrees){
			if (subTree.root instanceof Type)
			{
				type = (Type)subTree.root;
				break;
			}
		}
		if (type == null)
		{
			throw new Exception("Unable to create field declaration under: " + earleyTree.root.tag); // Should not get here
		}
		PumpNode pump = new PumpNode();
		List<Tree> fields = new ArrayList<>();
		/// Get all the variable names of this field declaration into one list
		List<String> variableNames = new ArrayList<>();
		fun.parser.Tree varConcatTree = earleyTree;
		while (varConcatTree.subtrees.size() > 0){
			variableNames.add(((Token)varConcatTree.subtrees.get(1).root).text);
			varConcatTree = varConcatTree.subtrees.get(2);
		}
		
		/// For each variable we create a tree containing its name (and the type as a child)
		for (String varName:variableNames)
		{
			fields.add(new Tree(new DeclField(type, varName), subAstTrees.toArray(new Tree[subAstTrees.size()])));
		}
		/// We create a fake tree that behaves like a pump - and is actually a collection of all the fields.
		/// This fake tree will be "folded" using the pump handling mechanism
		return new Tree(pump, fields.toArray(new Tree[fields.size()]));
	}
	
	private DeclMethod CreateDeclMethod(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		List<Statement> statements = new ArrayList<>();
		List<Parameter> formals = new ArrayList<>();
		Type type = null;
		for (Tree subTree:subAstTrees){
			if (subTree.root instanceof Statement)
			{
				statements.add((Statement)subTree.root);
			}
			else if (subTree.root instanceof Type) {
				type = (Type)subTree.root;
			}
			else if (subTree.root instanceof Parameter) {
				formals.add((Parameter)subTree.root);
			}
			else {
				throw new Exception("Unable to create method declartion AstNode under: " + earleyTree.root.tag); // Should not get here
			}
		}
		if (type == null)
		{
			throw new Exception("Unable to parse return type under create method declaration node"); // Should not get here
		}
		CheckEarleyTreeValues(earleyTree.subtrees, 3, 2, Token.class, "DeclMethod");
		String methodName = ((Token)earleyTree.subtrees.get(2).root).text;
		if (earleyTree.root.tag.equals("LibMethod")) {
			// If this is a Library method
			return new DeclLibraryMethod(type, methodName, formals);
		} else if (earleyTree.subtrees.get(0).subtrees.size()>0){
			// If this is a static method
			return new DeclStaticMethod(type, methodName, formals, statements);
		} else {
			return new DeclVirtualMethod(type, methodName, formals, statements);
		}
	}

	private Parameter CreateParameter(fun.parser.Tree earleyTree, Type type) throws Exception{
		int parameterNameIndex = 0;
		if (earleyTree.root.tag.equals("Formals")){
			parameterNameIndex = 1;
		} else if (earleyTree.root.tag.equals("TypeConcat")){
			parameterNameIndex = 2;
		} else {
			throw new Exception("Create parameter triggered by " + earleyTree.root.tag);
		}
		CheckEarleyTreeValues(earleyTree.subtrees, parameterNameIndex + 1, parameterNameIndex, Token.class, "Parameter");
		return new Parameter(type, ((Token)earleyTree.subtrees.get(parameterNameIndex).root).text);
	}
	
	private Type CreateType(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		if (earleyTree.subtrees.size()<1){
			throw new Exception("Sub Trees size in Type");
		}
		Word typeWord = earleyTree.subtrees.get(0).root;
		Type returnType = null;
		if (typeWord instanceof Token){
			// Not array type
			Token typeToken = (Token)typeWord;
			if (typeToken.tag.equals("CLASS_ID")){
				returnType = new ClassType(typeToken.line, typeToken.text);
			} else {
				returnType = new PrimitiveType(typeToken.line, PrimitiveType.DataType.valueOf(typeToken.text.toUpperCase( /*This is an ugly fix perhaps*/)));
			}
		} else if ((typeWord.tag.equals("Type") && subAstTrees.get(0).root instanceof Type)){
			CheckAstValues(subAstTrees, 1, 0, Type.class, "Type");
			returnType = (Type)subAstTrees.get(0).root;
			for (fun.parser.Tree stateSubTree:earleyTree.subtrees){
				if (stateSubTree.root.tag.equals("[")){
					returnType.incrementDimension();
				}
			}
		} else {
			throw new Exception("Unable to create Type AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return returnType;
	}

	// Statements 
	
	private LocalVariable CreateLocalVariable(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		CheckEarleyTreeValues(earleyTree.subtrees, 2, 1, Token.class, "Local Variable");
		Token idToken  = (Token)earleyTree.subtrees.get(1).root;
		Type type = (Type)subAstTrees.get(0).root;
		if (subAstTrees.size() <= 1){
			// Only declaration
			return new LocalVariable(idToken.line, type , idToken.text);
		} else {
			// + assignment
			CheckAstValues(subAstTrees, 2, 1, Expression.class, "Local Variable (Expr assignment)");
			Expression expr = (Expression)subAstTrees.get(1).root;
			return new LocalVariable(idToken.line, type , idToken.text, expr);
		}
	}
	
	private Statement CreateStmtWoExpr(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		Statement returnStmt = null;
		CheckEarleyTreeValues(earleyTree.subtrees, 1, 0, Word.class, earleyTree.root.tag);
		Word firstChildToken = (Word)earleyTree.subtrees.get(0).root;
		switch (firstChildToken.tag){
			case "break":
				if (firstChildToken instanceof Token)	
					returnStmt = new StmtBreak(((Token)firstChildToken).line);
				else
					throw new Exception("child is not Token in WithOutExpr");
				break;
			case "continue":
				if (firstChildToken instanceof Token)	
					returnStmt = new StmtContinue(((Token)firstChildToken).line);
				else
					throw new Exception("child is not Token in WithOutExpr");
				break;
			case "Call":
				CheckAstValues(subAstTrees, 1, 0, Call.class, earleyTree.root.tag);
				Call call = (Call)subAstTrees.get(0).root;
				returnStmt = new StmtCall(call);
				break;
			default:
				throw new Exception("Unable to create StmtWoExpr AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return returnStmt;
	}
	
	private StmtReturn CreateReturnStmt(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		if (subAstTrees.size() == 0){
			CheckEarleyTreeValues(earleyTree.subtrees, 1, 0, Token.class, "ReturnStmt");
			return new StmtReturn(((Token)earleyTree.subtrees.get(0).root).line);
		} else {
			CheckAstValues(subAstTrees, 1, 0, Expression.class, "ReturnStmt");
			Expression expr = (Expression)subAstTrees.get(0).root;
			return new StmtReturn(expr.getLine(), expr);
		}
	}
	
	private StmtAssignment CreateStmtAssignment(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		CheckAstValues(subAstTrees, 2, 0, Ref.class, "StmtAssignment");
		CheckAstValues(subAstTrees, 2, 1, Expression.class, "StmtAssignment");
		return new StmtAssignment((Ref)subAstTrees.get(0).root, (Expression)subAstTrees.get(1).root);
	}

	private StmtBlock CreateStmtBlock(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		List<Statement> statements = new ArrayList<>();
		for (Tree subAstTree:subAstTrees){
			if (subAstTree.root instanceof Statement){
				statements.add((Statement)subAstTree.root);
			}
		}
		CheckEarleyTreeValues(earleyTree.subtrees, 1, 0, Token.class, "StmtBlock");
		Token openingCurly = (Token)earleyTree.subtrees.get(0).root;
		return new StmtBlock(openingCurly.line, statements); 
	}
	
	private StmtWhile CreateWhileStmt(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		StmtWhile whileStmt = null;
		CheckAstValues(subAstTrees, 2, 0, Expression.class, "StmtWhile");
		CheckAstValues(subAstTrees, 2, 1, Statement.class, "StmtWhile");
		Expression condition = (Expression)subAstTrees.get(0).root;
		Statement whileOperation = (Statement)subAstTrees.get(1).root;
		whileStmt = new StmtWhile(condition, whileOperation);
		return whileStmt;
	}
	
	private StmtIf CreateIfStmt(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		StmtIf stmtIf = null;
		CheckAstValues(subAstTrees, 2, 0, Expression.class, "StmtIf");
		CheckAstValues(subAstTrees, 2, 1, Statement.class, "StmtIf");
		Expression condition = (Expression)subAstTrees.get(0).root;
		Statement ifOperation = (Statement)subAstTrees.get(1).root;
		if (earleyTree.subtrees.size() == 5){
			// if ( Expr ) Stmt
			stmtIf = new StmtIf(condition, ifOperation);
		} else if (earleyTree.subtrees.size() == 7) {
			// if ( Expr ) IfElsePump else Stmt
			CheckAstValues(subAstTrees, 3, 2, Statement.class, "StmtIf (Else)");
			Statement elseOperation = (Statement)subAstTrees.get(2).root;
			stmtIf = new StmtIf(condition, ifOperation, elseOperation);
		} else {
			throw new Exception("Unable to create IfStmt AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return stmtIf;
	}
	
	// Expressions
	
	private Ref CreateRef(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception {
		Ref returnRef = null;
		if (earleyTree.subtrees.size() == 1){
			// ID
			CheckEarleyTreeValues(earleyTree.subtrees, 1, 0, Token.class, "Ref");
			Token idToken = (Token)earleyTree.subtrees.get(0).root;
			returnRef = new RefVariable(idToken.line, idToken.text);
		} else if (earleyTree.subtrees.size() == 3){
			// Expr . ID
			CheckAstValues(subAstTrees, 1, 0, Expression.class, "Ref");
			Expression expr = (Expression)subAstTrees.get(0).root;
			CheckEarleyTreeValues(earleyTree.subtrees, 3, 2, Token.class, "Ref (Expr.ID");
			Token idToken = (Token)earleyTree.subtrees.get(2).root;
			returnRef = new RefField(expr.getLine(), expr, idToken.text);
		} else if (earleyTree.subtrees.size() == 4){
			// Expr [ Expr ]
			CheckAstValues(subAstTrees, 2, 0, Expression.class, "Ref Expr [Expr]");
			CheckAstValues(subAstTrees, 2, 1, Expression.class, "Ref Expr [Expr] - inner");
			Expression arrExpr = (Expression)subAstTrees.get(0).root;
			Expression idxExpr = (Expression)subAstTrees.get(1).root;
			returnRef = new RefArrayElement(arrExpr, idxExpr);
		} else {
			throw new Exception("Unable to create Ref AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return returnRef;
	}
	
	private Expression CreateNewExpr(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception {
		Expression returnExpr = null;
		if (earleyTree.subtrees.size() == 1){
			/* this means it is a dummy node */
			CheckAstValues(subAstTrees, 1, 0, Expression.class, earleyTree.root.tag);
			Expression childExpression = (Expression)subAstTrees.get(0).root;
			subAstTrees.clear();
			return childExpression;
		}
		if (earleyTree.subtrees.size() == 5) {
			/* new Type [ Expr ]  == new array */
			CheckAstValues(subAstTrees, 2, 0, Type.class, earleyTree.root.tag);
			Type type=(Type)subAstTrees.get(0).root;
			CheckAstValues(subAstTrees, 2, 1, Expression.class, earleyTree.root.tag);
			Expression size = (Expression)subAstTrees.get(1).root;
			returnExpr = new NewArray(type, size);
		} else if (earleyTree.subtrees.size() == 4) {
			/* new CLASS-ID ( ) */
			CheckEarleyTreeValues(earleyTree.subtrees, 2, 0, Token.class, earleyTree.root.tag);
			CheckEarleyTreeValues(earleyTree.subtrees, 2, 1, Token.class, earleyTree.root.tag);
			Token newToken  = (Token)earleyTree.subtrees.get(0).root;
			Token classIdToken = (Token)earleyTree.subtrees.get(1).root;
			returnExpr = new NewInstance(newToken.line, classIdToken.text); 
		} else {
			throw new Exception("Unable to create NewExpr AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return returnExpr;
	}
	
	private Expression CreateTermExpr(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception {
		Expression returnExpr = null;
		if (earleyTree.subtrees.size() == 1) {
			/* Call | this | Literal | Location*/
			switch (earleyTree.root.tag) {
				case "this":
					CheckEarleyTreeValues(earleyTree.subtrees, 1, 0, Token.class, earleyTree.root.tag);
					Token token  = (Token)earleyTree.subtrees.get(0).root;;
					returnExpr = new This(token.line);
					break;
				default:
					// Dummy node
					CheckAstValues(subAstTrees, 1, 0, Expression.class, earleyTree.root.tag);
					returnExpr = (Expression)subAstTrees.get(0).root;
					subAstTrees.clear();
			}
		} else if (earleyTree.subtrees.size() == 3) {
			/* FinExpr . length*/
			CheckAstValues(subAstTrees, 1, 0, Expression.class, earleyTree.root.tag);
			Expression arrayExpr = (Expression)subAstTrees.get(0).root;
			returnExpr = new Length(arrayExpr.getLine(), arrayExpr);
		} else {
			throw new Exception("Unable to create TermExpr AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return returnExpr;
	}
	
	private Expression CreateBinaryExpr(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		if (earleyTree.subtrees.size() == 1){
			/* this means it is a dummy node */
			CheckAstValues(subAstTrees, 1, 0, Expression.class, earleyTree.root.tag);
			Expression childExpression = (Expression)subAstTrees.get(0).root;
			subAstTrees.clear();
			return childExpression;
		} else if (earleyTree.subtrees.size() == 3) {
			/* get action */
			CheckEarleyTreeValues(earleyTree.subtrees, 3, 1, Token.class, earleyTree.root.tag);
			Token opToken = (Token)earleyTree.subtrees.get(1).root;
			BinaryOp.BinaryOps op = BinaryOp.BinaryOps.find(opToken.text);
			
			/* get operands */
			CheckAstValues(subAstTrees, 2, 0, Expression.class, earleyTree.root.tag);
			CheckAstValues(subAstTrees, 2, 1, Expression.class, earleyTree.root.tag);
			Expression firstOperand = (Expression)subAstTrees.get(0).root;
			Expression secondOperand = (Expression)subAstTrees.get(1).root;
			
			return new BinaryOp(opToken.line, firstOperand, op, secondOperand);
		} else{
			throw new Exception("binary op number of children does not match the program logic");
		}
	}
	
	private Expression CreateUnaryExpr(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception{
		if (earleyTree.subtrees.size() == 1){
			/* this means it is a dummy node */
			CheckAstValues(subAstTrees, 1, 0, Expression.class, earleyTree.root.tag);
			Expression childExpression = (Expression)subAstTrees.get(0).root;
			subAstTrees.clear();
			return childExpression;
		} else if (earleyTree.subtrees.size() == 3) {
			// UnSymbol UnSymbolPump Expr
			CheckAstValues(subAstTrees, 1, 0, Expression.class, earleyTree.root.tag);
			Expression expression = (Expression)subAstTrees.get(0).root;
			
			// Calculate right most unary opeartion
			fun.parser.Tree unSymbolTree = earleyTree.subtrees.get(1);
			CheckEarleyTreeValues(unSymbolTree.subtrees, 1, 0, Token.class, earleyTree.root.tag);
			Token opToken = ((Token)unSymbolTree.subtrees.get(0).root);
			UnaryOp.UnaryOps unaryOperation = UnaryOp.UnaryOps.find(opToken.text);
			expression = new UnaryOp(opToken.line, unaryOperation, expression);
			
			fun.parser.Tree unarySymbolPumpTree = earleyTree.subtrees.get(0);
			// Calculate composition of unary expression (recurse on unary symbol pump)
			while (unarySymbolPumpTree.subtrees.size() > 1){
				unSymbolTree = unarySymbolPumpTree.subtrees.get(1);
				CheckEarleyTreeValues(unSymbolTree.subtrees, 2, 1, Token.class, earleyTree.root.tag);
				opToken = ((Token)unSymbolTree.subtrees.get(0).root);
				unaryOperation = UnaryOp.UnaryOps.find(opToken.text); 
				expression = new UnaryOp(opToken.line,unaryOperation,expression);
				unarySymbolPumpTree = unarySymbolPumpTree.subtrees.get(0);
			}
			
			return expression;
		} else {
			throw new Exception("unary expression invalid");
		}
	}
	
	private Expression CreateLiteral(fun.parser.Tree earleyTree, List<Tree> subAstTrees) throws Exception {
		CheckEarleyTreeValues(earleyTree.subtrees, 1, 0, Token.class, earleyTree.root.tag);
		Token token  = (Token)earleyTree.subtrees.get(0).root;
		DataType dataType = null;
		switch (token.tag) {
			case "INTEGER":
				dataType = PrimitiveType.DataType.INT;
				try{
					Integer.parseInt(token.text);
				}
				catch (NumberFormatException nfe){
					String error=String.format("%d:%d : syntax error; numeric literal out of range: %s",token.line,token.column,token.text);
					throw new NumberFormatException(error);
				}
				break;
			case "STRING":
				dataType = PrimitiveType.DataType.STRING;
				token.text= parseStringType(token.text);
				break;
			case "false":
			case "true":
				dataType = PrimitiveType.DataType.BOOLEAN;
				break;	
			case "null":
				// TODO: what is PrimitiveType.DataType of null? 
				dataType = PrimitiveType.DataType.VOID;
				break;
			default:
				throw new Exception("Unable to create Literal AstNode under: " + earleyTree.root.tag); // Should not get here
		}
		return new Literal(token.line, dataType, token.text);
	}
	
	// Helpers
	
	private void CheckEarleyTreeValues(List<fun.parser.Tree> collection, int minimumSize, int idx, Class<?> type, String objectName)  throws Exception {
		if (collection.size()<minimumSize){
			throw new Exception("Early tree SubTrees size in " + objectName);
		}
		if (!(type.isInstance(collection.get(idx).root))){
			throw new Exception("child is not " + type.getName() +" in " + objectName);
		}
	}
	
	private void CheckAstValues(List<Tree> collection, int minimumSize, int idx, Class<?> type, String objectName) throws Exception {
		if (collection.size()<minimumSize){
			throw new Exception("Ast tree SubTrees size in " + objectName);
		}
		if (!(type.isInstance(collection.get(idx).root))){
			throw new Exception("child is not " + type.getName() +" in " + objectName);
		}
	}
	
	private String parseStringType(String s){
		s=s.substring(1,s.length()-1);
		s=s.replaceAll("\\\\n", "\\\n").replaceAll("\\\\t","\\\t");
		s=s.replaceAll("\\\\\\\"", "\\\"").replaceAll("\\\\\\\\", "\\\\");
		return s;
		
	}
	
	/*void processToken(Token token) {
		switch (token.tag) {
		case "#": 
			state.stack.push(new Tree(token));
			break;
		case "◇":
			Tree rhs = state.stack.pop();
			Tree lhs = state.stack.pop();
			state.stack.push(new Tree(token,
					new Tree[] { lhs, rhs }));
			break;
		default:
			throw new Error("Parse error");
		}
	}

	public double eval(Tree t) {
		Token r = (Token)t.root;
		switch (r.tag) {
		case "#": return Double.parseDouble(r.text);
		case "◇": 
			Double a = eval(t.subtrees[0]),
			       b = eval(t.subtrees[1]);
			switch (r.text) {
			case "+": return a + b;
			case "-": return a - b;
			case "*": return a * b;
			case "/": return a / b;
			case "^": return Math.pow(a, b);
			default:
				// should never get here 
				throw new Error("corrupted ast!");
			}
		default:
			// nor here 
			throw new Error("corrupted ast!");
		}
	}
	
	public String infix(Tree t) {
		Token r = (Token)t.root;
		if (t.subtrees.length == 0) {
			return r.text;
		}
		else {
			String a = infix_subex(t.subtrees[0]),
			       b = infix_subex(t.subtrees[1]);
			return a + " " + r.text + " " + b;
		}
	}
	
	String infix_subex(Tree t) {
		String a = infix(t); 
		if (t.subtrees.length > 0)
			a = "(" + a + ")";
		return a;
	}*/
}